/*  
  -- The Lime II Project -- 

  A tuplespaces-based middleware for coordinating agents and mobile hosts.
  Copyright (C) 2005.
  Gian Pietro Picco, Amy L. Murphy, Lorenzo Bellini.

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  Lesser General Public License for more details.

  You should have received this copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 
*/

package lime2;
import java.util.Vector;

/**
 * Models a priority scheduler. 
 * <br>
 * A priority scheduler provides support for Quality-Of-Service. Objects are scheduled according to their priority 
 * level; <code>0</code> is the highest priority level, <code>1</code> is the second highest priority level, etc..
 * objects with the same priority level are just enqueued (FIFO order). 
 * <br>
 * When you try to retrieve an object, it blocks until one or more elements show up and it returns the object with the
 * highest priority level - if this doesn't violate the corresponding "priority limit". Otherwise the returned object 
 * is the one with the next higher priority level.. and so on. 
 * <br>
 * Priority limits guarantee that no more than <code>P[N]</code> objects with priority level <code>N</code> can be 
 * returned before an object of priority level <code>N - 1</code> is returned (if at least one object of priority
 * level <code>N - 1</code> is present).
 * <br>
 * The priority limit for the lowest priority level has no sense and thus is not considered; a negative value for a
 * priority limit means <i>infinite</i>, value zero is illegal (except for the lowest priority level). 
 * 
 * @author Gian Pietro Picco
 * @author Amy Murphy
 * @author Lorenzo Bellini
 */

public class PriorityScheduler 
{
 // private: queues	for the different priority levels (index 0 is the highest priority level, etc..) 
 private Vector[] queues;
 
 // private: priority limits
  private int[] limits;
 
 // private: rounds already executed for this queue (must be < corresponding priority limit)
 private int[] rounds;
 
 // private: number of priority levels
 private int lastIndex;
 
 /** 
  * Constructor method. Given an array of priority limits, the priority scheduler will use the same number of priority
  * levels. The first element of the array is the priority limit for the highest priority level, the second one for
  * the second highest priority level, etc.. The priority limit for the lowest priority level has no sense and thus is
  * not considered. A negative value for a priority limit means <i>infinite</i>, value zero is illegal (except for the
  * lowest priority level).  
  * 
  * @param lim array of priority limits 
  */
 public PriorityScheduler(int[] lim) 
 { 
  // parameter checking	
  lastIndex = lim.length - 1;
  for (int i = 0; i < lastIndex; i++) if (lim[i] == 0) throw new IllegalArgumentException("value zero is illegal");
  // initializations 
  limits = lim;
  queues = new Vector[limits.length];
  rounds = new int[limits.length];
  for (int i = 0; i < limits.length; i++) { queues[i] = new Vector(); rounds[i] = 0; }
 } 
 
 /**
  * Schedules an object at the given priority level. <code>0</code> is the highest priority level, <code>1</code> is
  * the second highest priority level, etc..
  * 
  * @param o object to schedule
  * @param priority level of priority
  */
 synchronized public void schedule(int priority, Object o) 
 {	
  queues[priority].addElement(o);
  notify();
 }

 /**
  * It blocks until one or more elements show up and returns the object with the highest priority level - if this 
  * doesn't violate the corresponding priority limit. Otherwise the returned object is the one with the next higher
  * priority level.. and so on. 
  * 
  * @return Object
  */
 synchronized public Object serve()
 { 	
  // auxiliary variables	
  int qq = -1;
  int rr = -1;
  // .. maybe we want something else to happen when the thread is interrupted
  while ((rr = qq = findFirstNonEmpty()) == -1) try { wait(); } catch (InterruptedException ie) { ie.printStackTrace(); }	
  
  // scheduling routine
  while ((qq != lastIndex) && (limits[qq] > 0))
  {
   rr = qq;	
   if (rounds[qq] < limits[qq]) { rounds[qq]++; qq = lastIndex; }
                           else { rounds[qq] = 0; while (qq != lastIndex && queues[++qq].isEmpty()); };  
  }
                           
  // returns Object
  return queues[rr].remove(0); 
 }
 
 // finds the non-empty queue with the highest priority level; if all queues are empty then -1 is returned
 private int findFirstNonEmpty() 
 {
  int i = 0;
  boolean found = false;
  while (!found && i < queues.length) if (queues[i].isEmpty()) i++; else found = true;  
  if (found) return i; else return -1; 	
 }
 
}
